def kmp(s: str):
    """
    求s的kmp数组
    """
    n = len(s)
    ret = [0] * n
    for i in range(1, n):
        j = ret[i - 1]
        while j > 0 and s[i] != s[j]:
            j = ret[j - 1]
        if s[i] == s[j]:
            j += 1
        ret[i] = j
    return ret
